<!DOCTYPE html>


<html lang="en">
  

    <head>
      <meta charset="utf-8" />
        
      <meta name="description" content="KeproZ的博客网站" />
      
      <meta
        name="viewport"
        content="width=device-width, initial-scale=1, maximum-scale=1"
      />
      <title> 饺子站</title>
  <meta name="generator" content="hexo-theme-ayer">
      
      <link rel="shortcut icon" href="/favicon.ico" />
       
<link rel="stylesheet" href="/dist/main.css">

      
<link rel="stylesheet" href="/css/fonts/remixicon.css">

      
<link rel="stylesheet" href="/css/custom.css">
 
      <script src="https://cdn.staticfile.org/pace/1.2.4/pace.min.js"></script>
       
 

      <link
        rel="stylesheet"
        href="https://cdn.jsdelivr.net/npm/@sweetalert2/theme-bulma@5.0.1/bulma.min.css"
      />
      <script src="https://cdn.jsdelivr.net/npm/sweetalert2@11.0.19/dist/sweetalert2.min.js"></script>

      <!-- mermaid -->
      
      <style>
        .swal2-styled.swal2-confirm {
          font-size: 1.6rem;
        }
      </style>
    </head>
  </html>
</html>


<body>
  <div id="app">
    
      
    <main class="content on">
      
<section class="cover">
    
      
      <a class="forkMe" href="https://github.com/Shen-Yu/hexo-theme-ayer"
        target="_blank"><img width="149" height="149" src="/images/forkme.png"
          class="attachment-full size-full" alt="Fork me on GitHub" data-recalc-dims="1"></a>
    
  <div class="cover-frame">
    <div class="bg-box">
      <img src="/images/cover1.jpg" alt="image frame" />
    </div>
    <div class="cover-inner text-center text-white">
      <h1><a href="/">饺子站</a></h1>
      <div id="subtitle-box">
        
        <span id="subtitle"></span>
        
      </div>
      <div>
        
      </div>
    </div>
  </div>
  <div class="cover-learn-more">
    <a href="javascript:void(0)" class="anchor"><i class="ri-arrow-down-line"></i></a>
  </div>
</section>



<script src="https://cdn.staticfile.org/typed.js/2.0.12/typed.min.js"></script>


<!-- Subtitle -->

  <script>
    try {
      var typed = new Typed("#subtitle", {
        strings: ['面朝大海，春暖花开', '愿你一生努力，一生被爱', '想要的都拥有，得不到的都释怀'],
        startDelay: 0,
        typeSpeed: 660,
        loop: true,
        backSpeed: 100,
        showCursor: true
      });
    } catch (err) {
      console.log(err)
    }
  </script>
  
<div id="main">
  <section class="outer">
  
  <ul class="ads">
    
        <li>
            <a target="_blank" rel="noopener" href="https://keproz.top">
                <img src="https://47.122.29.3:32890/down/YjNZSiqDqywz.jpg" width="300" alt="Keproz的个人空间">
            </a>
        </li>
    
</ul>
  
  
  

<div class="notice" style="margin-top:50px">
    <i class="ri-heart-fill"></i>
    <div class="notice-content" id="broad"></div>
</div>
<script type="text/javascript">
    fetch('https://v1.hitokoto.cn')
        .then(response => response.json())
        .then(data => {
            document.getElementById("broad").innerHTML = data.hitokoto;
        })
        .catch(console.error)
</script>

<style>
    .notice {
        padding: 20px;
        border: 1px dashed #e6e6e6;
        color: #969696;
        position: relative;
        display: inline-block;
        width: 100%;
        background: #fbfbfb50;
        border-radius: 10px;
    }

    .notice i {
        float: left;
        color: #999;
        font-size: 16px;
        padding-right: 10px;
        vertical-align: middle;
        margin-top: -2px;
    }

    .notice-content {
        display: initial;
        vertical-align: middle;
    }
</style>
  
  <article class="articles">
    
    
    
    
    <article
  id="post-算法"
  class="article article-type-post"
  itemscope
  itemprop="blogPost"
  data-scroll-reveal
>
  <div class="article-inner">
    
    <header class="article-header">
       
<h2 itemprop="name">
  <a class="article-title" href="/2024/02/25/%E7%AE%97%E6%B3%95/"
    >算法(Algorithm)</a> 
</h2>
 

      
    </header>
     
    <div class="article-meta">
      <a href="/2024/02/25/%E7%AE%97%E6%B3%95/" class="article-date">
  <time datetime="2024-02-25T08:58:03.148Z" itemprop="datePublished">2024-02-25</time>
</a>    
    </div>
      
    <div class="article-entry" itemprop="articleBody">
       
  <blockquote>
<p>本文为基于浙江大学陈越老师的数据结构课程的学习笔记</p>
</blockquote>
<h2 id="1-定义"><a href="#1-定义" class="headerlink" title="1. 定义"></a>1. 定义</h2><ul>
<li>一个有限指令集</li>
<li>接受一些输入（有些情况下不需要输入）</li>
<li>产生输出</li>
<li>一定在有限步骤之后终止</li>
<li>每一条指令必须<ul>
<li>有充分明确的目标，不可以有歧义</li>
<li>计算机能处理的范围之内</li>
<li>描述应不依赖于任何一种计算机语言以及具体的实现手段</li>
</ul>
</li>
</ul>
<h3 id="1-例：选择排序算法的伪码描述"><a href="#1-例：选择排序算法的伪码描述" class="headerlink" title="(1) 例：选择排序算法的伪码描述"></a>(1) 例：选择排序算法的伪码描述</h3><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">SelectionSort</span> <span class="params">(<span class="type">int</span> List[], <span class="type">int</span> N)</span></span><br><span class="line">&#123;<span class="comment">/*将N个整数List[0]…List[N-1]进行非递减排序*/</span></span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;N; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        MinPosition = ScanForMin(List, i, N<span class="number">-1</span>);</span><br><span class="line">        <span class="comment">/*从List[i]到List[N-1]中找最小元，并将其位置赋给MinPosition*/</span></span><br><span class="line">        Swap(List[i], List[MinPosition]);</span><br><span class="line">        <span class="comment">/*将从未排序部分的最小元换到有序部分的最后位置*/</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="2-算法效率"><a href="#2-算法效率" class="headerlink" title="2. 算法效率"></a>2. 算法效率</h2><h3 id="1-什么是算法效率"><a href="#1-什么是算法效率" class="headerlink" title="(1) 什么是算法效率"></a>(1) 什么是算法效率</h3><blockquote>
<p>除了正确性，算法的另外一个重要的特点就是<strong>效率Efficiency</strong>了。有两种算法效率：<strong>时间效率Time Efficiency</strong>和<strong>空间效率Space Effiency</strong>。时间效率也称为<strong>时间复杂度Time Complexity</strong>，指出算法运行有多快；空间效率有称为<strong>空间复杂度Space Complexity</strong>，指出算法需要多少额外的空间。</p>
</blockquote>
<h3 id="2-printN（空间复杂度）"><a href="#2-printN（空间复杂度）" class="headerlink" title="(2) printN（空间复杂度）"></a>(2) printN（空间复杂度）</h3><h4 id="a-循环"><a href="#a-循环" class="headerlink" title="a. 循环"></a>a. 循环</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="type">void</span> <span class="title function_">printN</span><span class="params">(<span class="type">int</span> N)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="type">int</span> i;</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">1</span>;i&lt;=N;i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,i);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span>;</span><br><span class="line">&#125; </span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="type">void</span> <span class="title function_">printN</span><span class="params">(<span class="type">int</span> N)</span>;</span><br><span class="line">	<span class="type">int</span> N;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;N);</span><br><span class="line">	printN(N);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>运行结果：<br><img src="https://img-blog.csdnimg.cn/1bdcf2cedf4c4e6daa44a4e542d1d25f.png" alt="循环与递归1"></p>
<h4 id="b-递归"><a href="#b-递归" class="headerlink" title="b. 递归"></a>b. 递归</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="type">void</span> <span class="title function_">printN</span><span class="params">(<span class="type">int</span> N)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="keyword">if</span>(N)</span><br><span class="line">	&#123;</span><br><span class="line">		printN(N<span class="number">-1</span>); </span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,N);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span>;</span><br><span class="line">&#125; </span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="type">int</span> N;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;N);</span><br><span class="line">	printN(N);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>运行结果：</strong></p>
<p><img src="https://img-blog.csdnimg.cn/2fce74fb989d4bb19ca74dfde5ed3285.png" alt="循环与递归2"></p>
<h4 id="注意："><a href="#注意：" class="headerlink" title="注意："></a>注意：</h4><p><strong>当输入100000时：</strong></p>
<p><strong>循环：</strong><br><img src="https://img-blog.csdnimg.cn/1d24bc1365724998a12887e0f021ad0d.png" alt="循环与递归3"></p>
<p><strong>递归：</strong><br><img src="https://img-blog.csdnimg.cn/848b941a50f54c37b28ca879749c7711.png" alt="循环与递归4"></p>
<h4 id="原因："><a href="#原因：" class="headerlink" title="原因："></a>原因：</h4><p>当一个非常简单的程序使用递归实现时，系统会分配大量的内存。<br>这是因为，每一次递归的实现中，系统都会重新为变量分配空间而不是覆盖原来的空间。<br>因此，当问题没有特别复杂，并不一定需要使用到递归程序时，应当避免使用递归程序，<br>尤其是递归次数多的程序，可能会造成内存分配的崩溃。</p>
<h4 id="结论："><a href="#结论：" class="headerlink" title="结论："></a>结论：</h4><p>解决问题方法的效率，跟<strong>空间的利用率</strong>有关。</p>
<h3 id="3-计算多项式值（时间复杂度）"><a href="#3-计算多项式值（时间复杂度）" class="headerlink" title="(3) 计算多项式值（时间复杂度）"></a>(3) 计算多项式值（时间复杂度）</h3><h4 id="a-直接算法"><a href="#a-直接算法" class="headerlink" title="a. 直接算法"></a>a. 直接算法</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">double</span> <span class="title function_">f</span><span class="params">(<span class="type">int</span> n,<span class="type">double</span> a[],<span class="type">double</span> x)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="type">int</span> i;</span><br><span class="line">	<span class="type">double</span> p = a[<span class="number">0</span>];</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">		p += (a[i]*<span class="built_in">pow</span>(x,i));</span><br><span class="line">	<span class="keyword">return</span> p;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="b-秦九韶算法"><a href="#b-秦九韶算法" class="headerlink" title="b. 秦九韶算法"></a>b. 秦九韶算法</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">double</span> <span class="title function_">f2</span><span class="params">(<span class="type">double</span> a[],<span class="type">int</span> n,<span class="type">double</span> x)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">double</span> result=a[n];</span><br><span class="line">    <span class="type">int</span> i;</span><br><span class="line">    <span class="keyword">for</span>(i=n;i&gt;=<span class="number">1</span>;i++)&#123;</span><br><span class="line">        result=a[i<span class="number">-1</span>]+x*result;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="注意：-1"><a href="#注意：-1" class="headerlink" title="注意："></a>注意：</h4><p>**clock()**：捕捉从程序开始运行到<code>clock()</code>被调用时所耗费的时间。这个时间单位是<code>clock tick</code>，即“时钟打点”。</p>
<p><strong>常数CLK_TCK</strong>：机器时钟每秒所走的时钟打点数。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;time.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="type">clock_t</span> start,stop;<span class="comment">//clock_t是clock()函数返回的变量类型</span></span><br><span class="line"></span><br><span class="line"><span class="type">double</span> duration;<span class="comment">//记录被测函数的运行时间，以秒为单位</span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="comment">//不在测试范围内的准备工作写在clock()调用之前</span></span><br><span class="line">	start = clock();<span class="comment">//开始计时 </span></span><br><span class="line">	MyFunction();<span class="comment">//把被测函数加在这里</span></span><br><span class="line">	stop = clock();</span><br><span class="line">	duration = ((<span class="type">double</span>) (stop-start))/CLK_TCK;</span><br><span class="line">	<span class="comment">//其他不在测试范围的处理写在后面，例如输出duration的值</span></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>; </span><br><span class="line">&#125; </span><br></pre></td></tr></table></figure>

<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;time.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;math.h&gt;</span></span></span><br><span class="line"><span class="type">clock_t</span> start,stop;</span><br><span class="line"><span class="type">double</span> duration;</span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAXN 10<span class="comment">//多项式最大项数，即多项式阶数+1</span></span></span><br><span class="line"><span class="type">double</span> <span class="title function_">f1</span><span class="params">(<span class="type">int</span> n,<span class="type">double</span> a[],<span class="type">double</span> x)</span>;</span><br><span class="line"><span class="type">double</span> <span class="title function_">f2</span><span class="params">(<span class="type">int</span> n,<span class="type">double</span> a[],<span class="type">double</span> x)</span>; </span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="type">int</span> i;</span><br><span class="line">	<span class="type">double</span> a[MAXN];<span class="comment">//储存多项式的系数</span></span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;MAXN;i++)</span><br><span class="line">		a[i] = (<span class="type">double</span>)i;</span><br><span class="line">	start = clock();</span><br><span class="line">	f1(MAXN<span class="number">-1</span>,a,<span class="number">1.1</span>);</span><br><span class="line">	stop = clock;</span><br><span class="line">	duration = ((<span class="type">double</span>)(stop-start))/CLK+TCK;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;ticks1 = %f\n&quot;</span>,(<span class="type">double</span>)(stop-start));</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;duration1 = %6.2e\n&quot;</span>,duration);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>让被测函数<strong>重复运行</strong>充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数<strong>平均每次</strong>运行的时间即可！</p>
<h4 id="原因：-1"><a href="#原因：-1" class="headerlink" title="原因："></a>原因：</h4><p>秦九韶算法最大的优点在于将求n次多项式的值转化为求n个一次多项式的值。 在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；对于计算机程序算法而言，加法比乘法的计算效率要高很多，因此该算法仍有极大的意义，用于减少CPU运算时间。</p>
<h4 id="结论：-1"><a href="#结论：-1" class="headerlink" title="结论："></a>结论：</h4><p>解决问题方法的效率，还跟算法的巧妙程度有关。</p>
<h2 id="3-算法复杂度进阶"><a href="#3-算法复杂度进阶" class="headerlink" title="3. 算法复杂度进阶"></a>3. 算法复杂度进阶</h2><h3 id="1-复杂度的渐进表示"><a href="#1-复杂度的渐进表示" class="headerlink" title="(1) 复杂度的渐进表示"></a>(1) 复杂度的渐进表示</h3><ul>
<li>$T(n)&#x3D;O(f(n))$ 表示存在常数 $C&gt;0,n_0&gt;0$ 使得当 $n≥n_0$ 时有 $T(n)≤C·f(n)$</li>
<li>$T(n)&#x3D;Ω(g(n))$ 表示存在常数 $C&gt;0,n_0&gt;0$ 使得当 $n≥n_0$ 时有 $T(n)≥C·g(n)$</li>
<li>$T(n)&#x3D;Θ(h(n))$ 表示同时有 $T(n)&#x3D;O(h(n))$ 和 $T(n)&#x3D;Ω(h(n))$</li>
</ul>
<p><strong>复杂度图表：</strong><br><img src="https://img-blog.csdnimg.cn/c799dfaa99724dcb87c6a4bba4c827cc.png" alt="复杂度图表"></p>
<p><strong>复杂度函数图：</strong><br><img src="https://img-blog.csdnimg.cn/3897a0cd644946888cc8820a4b44dda2.png" alt="复杂度函数图"></p>
<p><strong>每秒10亿指令计算机的运行时间表：</strong><br><img src="https://img-blog.csdnimg.cn/84bbd21bca324c90b6c648fadf6d9152.png" alt="复杂度运行时间表"></p>
<h3 id="2-复杂度分析便捷方法"><a href="#2-复杂度分析便捷方法" class="headerlink" title="(2) 复杂度分析便捷方法"></a>(2) 复杂度分析便捷方法</h3><ul>
<li>若两段算法分别有复杂度 $T_1(n)&#x3D;O(f_1(n))$ 和 $T_2(n)&#x3D;O(f_2(n))$，则<ul>
<li>$T_2(n)+T_2(n)&#x3D;max(O(f_1(n)),O(f_2(n)))$</li>
<li>$T_2(n)+T_2(n)&#x3D;O(f_1(n)×f_2(n))$</li>
</ul>
</li>
<li>若 $T_{1}(n)$ 是关于n的k阶多项式，那么 $T(n)&#x3D;Θ(n^k)$</li>
<li>一个<code>for</code>循环的时间复杂度等于循环次数乘以循环体代码的复杂度</li>
<li><code>if-else</code>结构的复杂度取决于<code>if</code>的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大</li>
</ul>
<h2 id="4-应用实例"><a href="#4-应用实例" class="headerlink" title="4.应用实例"></a>4.应用实例</h2><h3 id="最大子列和问题"><a href="#最大子列和问题" class="headerlink" title="最大子列和问题"></a>最大子列和问题</h3><p>给定N个整数的序列 ${A_1,A_2,…,A_N}$ ，求函数 $f(i,j)&#x3D;max{0,\sum_{k&#x3D;i}^jA_k}$ 的最大值（1≤i≤j≤K）</p>
<h4 id="算法1："><a href="#算法1：" class="headerlink" title="算法1："></a>算法1：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">MaxSubseqSum1</span><span class="params">(<span class="type">int</span> A[], <span class="type">int</span> N)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="type">int</span> ThisSum, MaxSum = <span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> i, j, k;</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;N; i++)</span><br><span class="line">	&#123;<span class="comment">/*i是子列左端位置*/</span></span><br><span class="line">		<span class="keyword">for</span>(j=i; j&lt;N; j++)</span><br><span class="line">		&#123;<span class="comment">/*j是子列右端位置*/</span></span><br><span class="line">			ThisSum = <span class="number">0</span>;<span class="comment">/*ThisSum是从A[i]到A[j]的子列和*/</span></span><br><span class="line">			<span class="keyword">for</span>(k=i; k&lt;=j; k++)</span><br><span class="line">				ThisSum += A[k];</span><br><span class="line">			<span class="keyword">if</span>(ThisSum &gt; MaxSum)<span class="comment">/*如果刚得到的这个子列和更大*/</span></span><br><span class="line">				MaxSum = ThisSum;<span class="comment">/*则更新结果*/</span></span><br><span class="line">		&#125;<span class="comment">/*j循环结束*/</span></span><br><span class="line">	&#125;<span class="comment">/*i循环结束*/</span></span><br><span class="line"><span class="keyword">return</span> MaxSum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>$$ T(N)&#x3D;O(N^3) $$</p>
<p><em>直观原因：三层for循环嵌套</em></p>
<h4 id="算法2："><a href="#算法2：" class="headerlink" title="算法2："></a>算法2：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">MaxSubseqSum2</span><span class="params">(<span class="type">int</span> A[], <span class="type">int</span> N)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="type">int</span> ThisSum, MaxSum = <span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> i,j;</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;N; i++)</span><br><span class="line">	&#123;<span class="comment">/*i是子列左端位置*/</span></span><br><span class="line">		ThisSum = <span class="number">0</span>;<span class="comment">/*ThisSum = 0;*/</span></span><br><span class="line">		<span class="keyword">for</span>(j=i; j&lt;N; j++)</span><br><span class="line">		&#123;<span class="comment">/*j是子列右端位置*/</span></span><br><span class="line">			ThisSum += A[j];</span><br><span class="line">			<span class="comment">/*对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可*/</span></span><br><span class="line">			<span class="keyword">if</span>(ThisSum &gt; MaxSum)<span class="comment">/*如果刚得到这个子列和更大*/</span></span><br><span class="line">				MaxSum = ThisSum;<span class="comment">/*则更新结果*/</span></span><br><span class="line">		&#125;<span class="comment">/*j循环结束*/</span></span><br><span class="line">	&#125;<span class="comment">/*i循环结束*/</span></span><br><span class="line"><span class="keyword">return</span> MaxSum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>$$ T(N)&#x3D;O(N^2) $$</p>
<p><em>直观原因：两层for循环嵌套</em></p>
<h4 id="算法3：分而治之"><a href="#算法3：分而治之" class="headerlink" title="算法3：分而治之"></a>算法3：分而治之</h4><p><img src="https://img-blog.csdnimg.cn/19939d256af64ef3aaac6c1cdb91b385.png" alt="分而治之"></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">Max3</span><span class="params">(<span class="type">int</span> A, <span class="type">int</span> B, <span class="type">int</span> C)</span></span><br><span class="line">&#123;<span class="comment">/*返回三个整数的最大值*/</span></span><br><span class="line">	<span class="keyword">return</span> (A &gt; B) ? (A &gt; C ? A : C) : (B &gt; C ? B : C);</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">int</span> <span class="title function_">DivideAndConquer</span><span class="params">(<span class="type">int</span> List[], <span class="type">int</span> left, <span class="type">int</span> right)</span></span><br><span class="line">&#123;<span class="comment">/*分治法求List[left]到List[right]的最大子列和*/</span></span><br><span class="line">	<span class="type">int</span> MaxLeftSum, MaxRightSum;</span><br><span class="line">	<span class="comment">/*存放左右子问题的解*/</span></span><br><span class="line">	<span class="type">int</span> MaxLeftBorderSum, MaxRightBorderSum;</span><br><span class="line">	<span class="comment">/*存放跨分界线的结果。*/</span></span><br><span class="line">	<span class="type">int</span> LeftBorderSum, RightBorderSum;</span><br><span class="line">	<span class="type">int</span> center, i;</span><br><span class="line">	<span class="keyword">if</span>(left == right)</span><br><span class="line">	&#123;<span class="comment">/*递归的终止条件，子列只有1个数字*/</span></span><br><span class="line">		<span class="keyword">if</span>(List[left] &gt; <span class="number">0</span>)</span><br><span class="line">			<span class="keyword">return</span> List[left];</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">    <span class="comment">/* “分”的过程 */</span></span><br><span class="line">	center = (left + right)/<span class="number">2</span>;</span><br><span class="line">	<span class="comment">/*找到中分点*/</span></span><br><span class="line">	MaxLeftSum = DivideAndConquer(List, left, center);</span><br><span class="line">	<span class="comment">/*递归求左子列和*/</span></span><br><span class="line">	MaxRightSum = DivideAndConquer(List, center+<span class="number">1</span>, right);</span><br><span class="line">	<span class="comment">/*递归求右子列和*/</span></span><br><span class="line">	MaxLeftBorderSum = <span class="number">0</span>;</span><br><span class="line">	LeftBorderSum = <span class="number">0</span>;</span><br><span class="line">	<span class="comment">/*求跨分界线的最大子列和*/</span></span><br><span class="line">	<span class="keyword">for</span>(i = center; i &gt;= left; i--)</span><br><span class="line">	&#123;</span><br><span class="line">		LeftBorderSum += List[i];</span><br><span class="line">		<span class="keyword">if</span> (LeftBorderSum &gt; MaxLeftBorderSum)</span><br><span class="line">			MaxLeftBorderSum = LeftBorderSum;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/*左边扫描结束*/</span></span><br><span class="line">	MaxRightBorderSum = <span class="number">0</span>;</span><br><span class="line">	RightBorderSum = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span>(i = center+<span class="number">1</span>; i &lt;= right; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		RightBorderSum += List[i];</span><br><span class="line">		<span class="keyword">if</span> (RightBorderSum &gt; MaxRightBorderSum)</span><br><span class="line">			MaxRightBorderSum = RightBorderSum;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/*右边扫描结束*/</span></span><br><span class="line">	<span class="keyword">return</span> Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);</span><br><span class="line">	<span class="comment">/*返回“治”的结果*/</span></span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/*此函数用于保持接口相同*/</span></span><br><span class="line"><span class="type">int</span> <span class="title function_">MaxSubseqSum3</span><span class="params">(<span class="type">int</span> List[], <span class="type">int</span> N)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="keyword">return</span> DivideAndConquer(List, <span class="number">0</span>, N<span class="number">-1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>$$ T(N)&#x3D;O(NlogN) $$</p>
<p><em>直观原因：</em><br>$$\begin{aligned}<br>T(N)&amp;&#x3D;2T(N&#x2F;2)+cN \	<br>&amp;&#x3D;2[2T(N&#x2F;2^2)+cN&#x2F;2]+cN \<br>&amp;&#x3D;2^kO(1)+ckN \<br>&amp;&#x3D;O(NlogN) \<br>\end{aligned}$$</p>
<p><em>T(1)&#x3D;O(1)，其中N&#x2F;2^k&#x3D;1</em></p>
<h4 id="算法4：在线处理"><a href="#算法4：在线处理" class="headerlink" title="算法4：在线处理"></a>算法4：在线处理</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">MaxSubseqSum4</span><span class="params">(<span class="type">int</span> A[], <span class="type">int</span> N)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="type">int</span> ThisSum, MaxSum;</span><br><span class="line">	<span class="type">int</span> i;</span><br><span class="line">	ThisSum = MaxSum = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;N; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		ThisSum += A[i];</span><br><span class="line">		<span class="comment">/*向右累加*/</span></span><br><span class="line">		<span class="keyword">if</span>(ThisSum &gt; MaxSum)</span><br><span class="line">			MaxSum = ThisSum;</span><br><span class="line">			<span class="comment">/*发现更大和则更新当前结果*/</span></span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(ThisSum &lt; <span class="number">0</span>)</span><br><span class="line">		<span class="comment">/*如果当前子列和为负*/</span></span><br><span class="line">			ThisSum = <span class="number">0</span>;</span><br><span class="line">		<span class="comment">/*则不可能使后面的部分和增大，抛弃之*/</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> MaxSum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>$$ T(N)&#x3D;O(N) $$</p>
<p><em>直观原因：一层for循环</em></p>
<p>“<code>在线</code>”的意思是指每输入一个数据就进行<code>即时处理</code>，在任何一个地方中止输入，算法都能正确给出当前的解。</p>
<h4 id="运行时间比较"><a href="#运行时间比较" class="headerlink" title="运行时间比较"></a>运行时间比较</h4><p><img src="https://img-blog.csdnimg.cn/dfc299c4b33248b69c1d9e4130ed5e48.png" alt="运行时间比较"></p>
<hr>
<h2 id="参考资料："><a href="#参考资料：" class="headerlink" title="参考资料："></a>参考资料：</h2><p><a target="_blank" rel="noopener" href="https://www.icourse163.org/learn/ZJU-93001?tid=1468077441#/learn/announce">数据结构：什么是算法</a></p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/wangxufa/article/details/121198034">算法效率分析——夜雨风云的博客</a></p>
<p><a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E7%A7%A6%E4%B9%9D%E9%9F%B6%E7%AE%97%E6%B3%95/449196">秦九韶算法的百度百科</a></p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/YelloJesse/article/details/82312659">最大子列和问题——YelloJesse的博客</a></p>
 
      <!-- reward -->
      
    </div>
    

    <!-- copyright -->
    
    <footer class="article-footer">
       
    </footer>
  </div>

   
   
  
</article>

    
    <article
  id="post-hello-world"
  class="article article-type-post"
  itemscope
  itemprop="blogPost"
  data-scroll-reveal
>
  <div class="article-inner">
    
    <header class="article-header">
       
<h2 itemprop="name">
  <a class="article-title" href="/2024/02/25/hello-world/"
    >Hello World</a> 
</h2>
 

      
    </header>
     
    <div class="article-meta">
      <a href="/2024/02/25/hello-world/" class="article-date">
  <time datetime="2024-02-25T08:54:43.880Z" itemprop="datePublished">2024-02-25</time>
</a>    
    </div>
      
    <div class="article-entry" itemprop="articleBody">
       
  <p>Welcome to <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a>! This is your very first post. Check <a target="_blank" rel="noopener" href="https://hexo.io/docs/">documentation</a> for more info. If you get any problems when using Hexo, you can find the answer in <a target="_blank" rel="noopener" href="https://hexo.io/docs/troubleshooting.html">troubleshooting</a> or you can ask me on <a target="_blank" rel="noopener" href="https://github.com/hexojs/hexo/issues">GitHub</a>.</p>
<h2 id="Quick-Start"><a href="#Quick-Start" class="headerlink" title="Quick Start"></a>Quick Start</h2><h3 id="Create-a-new-post"><a href="#Create-a-new-post" class="headerlink" title="Create a new post"></a>Create a new post</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo new <span class="string">&quot;My New Post&quot;</span></span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/writing.html">Writing</a></p>
<h3 id="Run-server"><a href="#Run-server" class="headerlink" title="Run server"></a>Run server</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo server</span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/server.html">Server</a></p>
<h3 id="Generate-static-files"><a href="#Generate-static-files" class="headerlink" title="Generate static files"></a>Generate static files</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo generate</span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/generating.html">Generating</a></p>
<h3 id="Deploy-to-remote-sites"><a href="#Deploy-to-remote-sites" class="headerlink" title="Deploy to remote sites"></a>Deploy to remote sites</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo deploy</span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/one-command-deployment.html">Deployment</a></p>
 
      <!-- reward -->
      
    </div>
    

    <!-- copyright -->
    
    <footer class="article-footer">
       
    </footer>
  </div>

   
   
  
</article>

    
  </article>
  

  
</section>
</div>

      <footer class="footer">
  <div class="outer">
    <ul>
      <li>
        Copyrights &copy;
        2015-2024
        <i class="ri-heart-fill heart_icon"></i> John Doe
      </li>
    </ul>
    <ul>
      <li>
        
      </li>
    </ul>
    <ul>
      <li>
        
        
        <span>
  <span><i class="ri-user-3-fill"></i>Visitors:<span id="busuanzi_value_site_uv"></span></span>
  <span class="division">|</span>
  <span><i class="ri-eye-fill"></i>Views:<span id="busuanzi_value_page_pv"></span></span>
</span>
        
      </li>
    </ul>
    <ul>
      
    </ul>
    <ul>
      
    </ul>
    <ul>
      <li>
        <!-- cnzz统计 -->
        
        <script type="text/javascript" src='https://s9.cnzz.com/z_stat.php?id=1278069914&amp;web_id=1278069914'></script>
        
      </li>
    </ul>
  </div>
</footer>    
    </main>
    <div class="float_btns">
      <div class="totop" id="totop">
  <i class="ri-arrow-up-line"></i>
</div>

<div class="todark" id="todark">
  <i class="ri-moon-line"></i>
</div>

    </div>
    <aside class="sidebar on">
      <button class="navbar-toggle"></button>
<nav class="navbar">
  
  <div class="logo">
    <a href="/"><img src="/images/ayer-side.svg" alt="饺子站"></a>
  </div>
  
  <ul class="nav nav-main">
    
    <li class="nav-item">
      <a class="nav-item-link" href="/">主页</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/archives">归档</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/categories">分类</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags">标签</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E6%97%85%E8%A1%8C/">旅行</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" target="_blank" rel="noopener" href="http://shenyu-vip.lofter.com">摄影</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/friends">友链</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/2019/about">关于我</a>
    </li>
    
  </ul>
</nav>
<nav class="navbar navbar-bottom">
  <ul class="nav">
    <li class="nav-item">
      
      <a class="nav-item-link nav-item-search"  title="Search">
        <i class="ri-search-line"></i>
      </a>
      
      
      <a class="nav-item-link" target="_blank" href="/atom.xml" title="RSS Feed">
        <i class="ri-rss-line"></i>
      </a>
      
    </li>
  </ul>
</nav>
<div class="search-form-wrap">
  <div class="local-search local-search-plugin">
  <input type="search" id="local-search-input" class="local-search-input" placeholder="Search...">
  <div id="local-search-result" class="local-search-result"></div>
</div>
</div>
    </aside>
    <div id="mask"></div>

<!-- #reward -->
<div id="reward">
  <span class="close"><i class="ri-close-line"></i></span>
  <p class="reward-p"><i class="ri-cup-line"></i>请我喝杯咖啡吧~</p>
  <div class="reward-box">
    
    <div class="reward-item">
      <img class="reward-img" src="/images/alipay.jpg">
      <span class="reward-type">支付宝</span>
    </div>
    
    
    <div class="reward-item">
      <img class="reward-img" src="/images/wechat.jpg">
      <span class="reward-type">微信</span>
    </div>
    
  </div>
</div>
    
<script src="/js/jquery-3.6.0.min.js"></script>
 
<script src="/js/lazyload.min.js"></script>

<!-- Tocbot -->

<script src="https://cdn.staticfile.org/jquery-modal/0.9.2/jquery.modal.min.js"></script>
<link
  rel="stylesheet"
  href="https://cdn.staticfile.org/jquery-modal/0.9.2/jquery.modal.min.css"
/>
<script src="https://cdn.staticfile.org/justifiedGallery/3.8.1/js/jquery.justifiedGallery.min.js"></script>

<script src="/dist/main.js"></script>

<!-- ImageViewer -->
 <!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>

    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">

        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                <!--  Controls are self-explanatory. Order can be changed. -->

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" style="display:none" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div>

<link rel="stylesheet" href="https://cdn.staticfile.org/photoswipe/4.1.3/photoswipe.min.css">
<link rel="stylesheet" href="https://cdn.staticfile.org/photoswipe/4.1.3/default-skin/default-skin.min.css">
<script src="https://cdn.staticfile.org/photoswipe/4.1.3/photoswipe.min.js"></script>
<script src="https://cdn.staticfile.org/photoswipe/4.1.3/photoswipe-ui-default.min.js"></script>

<script>
    function viewer_init() {
        let pswpElement = document.querySelectorAll('.pswp')[0];
        let $imgArr = document.querySelectorAll(('.article-entry img:not(.reward-img)'))

        $imgArr.forEach(($em, i) => {
            $em.onclick = () => {
                // slider展开状态
                // todo: 这样不好，后面改成状态
                if (document.querySelector('.left-col.show')) return
                let items = []
                $imgArr.forEach(($em2, i2) => {
                    let img = $em2.getAttribute('data-idx', i2)
                    let src = $em2.getAttribute('data-target') || $em2.getAttribute('src')
                    let title = $em2.getAttribute('alt')
                    // 获得原图尺寸
                    const image = new Image()
                    image.src = src
                    items.push({
                        src: src,
                        w: image.width || $em2.width,
                        h: image.height || $em2.height,
                        title: title
                    })
                })
                var gallery = new PhotoSwipe(pswpElement, PhotoSwipeUI_Default, items, {
                    index: parseInt(i)
                });
                gallery.init()
            }
        })
    }
    viewer_init()
</script> 
<!-- MathJax -->

<!-- Katex -->

<!-- busuanzi  -->
 
<script src="/js/busuanzi-2.3.pure.min.js"></script>
 
<!-- ClickLove -->

<!-- ClickBoom1 -->

<!-- ClickBoom2 -->

<!-- CodeCopy -->
 
<link rel="stylesheet" href="/css/clipboard.css">
 <script src="https://cdn.staticfile.org/clipboard.js/2.0.10/clipboard.min.js"></script>
<script>
  function wait(callback, seconds) {
    var timelag = null;
    timelag = window.setTimeout(callback, seconds);
  }
  !function (e, t, a) {
    var initCopyCode = function(){
      var copyHtml = '';
      copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
      copyHtml += '<i class="ri-file-copy-2-line"></i><span>COPY</span>';
      copyHtml += '</button>';
      $(".highlight .code pre").before(copyHtml);
      $(".article pre code").before(copyHtml);
      var clipboard = new ClipboardJS('.btn-copy', {
        target: function(trigger) {
          return trigger.nextElementSibling;
        }
      });
      clipboard.on('success', function(e) {
        let $btn = $(e.trigger);
        $btn.addClass('copied');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-checkbox-circle-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPIED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-checkbox-circle-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
      clipboard.on('error', function(e) {
        e.clearSelection();
        let $btn = $(e.trigger);
        $btn.addClass('copy-failed');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-time-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPY FAILED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-time-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
    }
    initCopyCode();
  }(window, document);
</script>
 
<!-- CanvasBackground -->

<script>
  if (window.mermaid) {
    mermaid.initialize({ theme: "forest" });
  }
</script>


    
    

  </div>
</body>

</html>